def managehall(s,f):
    n=len(s)
    cnt=1
    q=[]
    for i in s:
        q.append( (i,cnt,'s') ) #(start time, activity, 's')
        cnt+=1
    cnt=1
    for i in f:
        q.append( (i,cnt,'f') ) #(finish time, activity, 'f')
        cnt+=1
    q.sort()
    where=dict() #activity:hall
    halls_free=[i for i in xrange(n-1,0,-1)] #n-1,n-2,...,1
    maxhall=0
    for t in q:
        if t[2]=='s':
            activity=t[1]
            hall=halls_free.pop()
            if hall>maxhall:
                maxhall=hall
            where[activity]=hall
            print 'activity {0:2d} uses hall {1}'.format(activity,hall)
        else: #t[1]='f'
            activity=t[1]
            hall=where[activity]
            halls_free.append(hall)
    print 'Need',maxhall,'halls'

if __name__=='__main__':
    s=[1,3,0,5,3,5,6,8,8,2,12]
    f=[4,5,6,7,8,9,10,11,12,13,14]
    print 's:', s
    print 'f:', f
    managehall(s,f)
